/*
 * Copyright 2020 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License,
 * version 2.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at:
 *
 *   https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */
package io.netty.buffer;

import static io.netty.buffer.PoolThreadCache.*;

/**
 * SizeClasses requires {@code pageShifts} to be defined prior to inclusion,
 * and it in turn defines:
 * <p>
 *   LOG2_SIZE_CLASS_GROUP: Log of size class count for each size doubling.
 *   LOG2_MAX_LOOKUP_SIZE: Log of max size class in the lookup table.
 *   sizeClasses: Complete table of [index, log2Group, log2Delta, nDelta, isMultiPageSize,
 *                 isSubPage, log2DeltaLookup] tuples.
 *     index: Size class index.
 *     log2Group: Log of group base size (no deltas added).
 *     log2Delta: Log of delta to previous size class.
 *     nDelta: Delta multiplier.
 *     isMultiPageSize: 'yes' if a multiple of the page size, 'no' otherwise.
 *     isSubPage: 'yes' if a subpage size class, 'no' otherwise.
 *     log2DeltaLookup: Same as log2Delta if a lookup table size class, 'no'
 *                      otherwise.
 * <p>
 *   nSubpages: Number of subpages size classes.
 *   nSizes: Number of size classes.
 *   nPSizes: Number of size classes that are multiples of pageSize.
 *
 *   smallMaxSizeIdx: Maximum small size class index.
 *
 *   lookupMaxclass: Maximum size class included in lookup table.
 *   log2NormalMinClass: Log of minimum normal size class.
 * <p>
 *   The first size class and spacing are 1 << LOG2_QUANTUM.
 *   Each group has 1 << LOG2_SIZE_CLASS_GROUP of size classes.
 *
 *   size = 1 << log2Group + nDelta * (1 << log2Delta)
 *
 *   The first size class has an unusual encoding, because the size has to be
 *   split between group and delta*nDelta.
 *
 *   If pageShift = 13, sizeClasses looks like this:
 *
 *   (index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup)
 * <p>
 *   ( 0,     4,        4,         0,       no,             yes,        4)
 *   ( 1,     4,        4,         1,       no,             yes,        4)
 *   ( 2,     4,        4,         2,       no,             yes,        4)
 *   ( 3,     4,        4,         3,       no,             yes,        4)
 * <p>
 *   ( 4,     6,        4,         1,       no,             yes,        4)
 *   ( 5,     6,        4,         2,       no,             yes,        4)
 *   ( 6,     6,        4,         3,       no,             yes,        4)
 *   ( 7,     6,        4,         4,       no,             yes,        4)
 * <p>
 *   ( 8,     7,        5,         1,       no,             yes,        5)
 *   ( 9,     7,        5,         2,       no,             yes,        5)
 *   ( 10,    7,        5,         3,       no,             yes,        5)
 *   ( 11,    7,        5,         4,       no,             yes,        5)
 *   ...
 *   ...
 *   ( 72,    23,       21,        1,       yes,            no,        no)
 *   ( 73,    23,       21,        2,       yes,            no,        no)
 *   ( 74,    23,       21,        3,       yes,            no,        no)
 *   ( 75,    23,       21,        4,       yes,            no,        no)
 * <p>
 *   ( 76,    24,       22,        1,       yes,            no,        no)
 */
abstract class SizeClasses implements SizeClassesMetric {

    static final int LOG2_QUANTUM = 4;

    private static final int LOG2_SIZE_CLASS_GROUP = 2;
    private static final int LOG2_MAX_LOOKUP_SIZE = 12;

    private static final int INDEX_IDX = 0;
    private static final int LOG2GROUP_IDX = 1;
    private static final int LOG2DELTA_IDX = 2;
    private static final int NDELTA_IDX = 3;
    private static final int PAGESIZE_IDX = 4;
    private static final int SUBPAGE_IDX = 5;
    private static final int LOG2_DELTA_LOOKUP_IDX = 6;

    private static final byte no = 0, yes = 1;

    protected SizeClasses(int pageSize, int pageShifts, int chunkSize, int directMemoryCacheAlignment) {
        this.pageSize = pageSize;//每一页的大小(默认为8192bit,即1kB,8192/8=1024Byte)
        this.pageShifts = pageShifts;//pageSize的最高位需要左移的次数(默认为13)。是8192的1位在13
        this.chunkSize = chunkSize;//这个chunk的大小(默认为16777216,即2MB)
        this.directMemoryCacheAlignment = directMemoryCacheAlignment;//主要是对于Huge这种直接分配的类型的数据将其对其为directMemoryCacheAlignment的倍数

        int group = log2(chunkSize) + 1 - LOG2_QUANTUM;//计算出group的数量

        //generate size classes
        //[index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup]
        sizeClasses = new short[group << LOG2_SIZE_CLASS_GROUP][7];//最多84个一维
        nSizes = sizeClasses();//初始化sizeclass二维数组

        //generate lookup table
        sizeIdx2sizeTab = new int[nSizes];//sizeIdx2sizeTab对应的是size存储大小。这个表格存的则是索引和对应的size的对应表格（其实就是上面表格中size那一列的数据）
        pageIdx2sizeTab = new int[nPSizes];//这个表格存储的是上面的表格中isMultiPages是1的对应的size的数据（主要用于监控的数据）
        idx2SizeTab(sizeIdx2sizeTab, pageIdx2sizeTab);

        size2idxTab = new int[lookupMaxSize >> LOG2_QUANTUM];//这个表格主要存储的是lookup下的size以每2B为单位存储一个size到其对应的size的缓存值(主要是对小数据类型的对应的idx的查找进行缓存)
        size2idxTab(size2idxTab);
    }

    protected final int pageSize;//每页大小
    protected final int pageShifts;//每页移动的次数
    protected final int chunkSize;//每个chunk的大小(默认为16777216,即2MB)
    protected final int directMemoryCacheAlignment;

    final int nSizes;//二维表格的一维数据长度
    int nSubpages;//子页size
    int nPSizes;//多页size

    int smallMaxSizeIdx;//small区块的最大索引值

    private int lookupMaxSize;

    private final short[][] sizeClasses;

    private final int[] pageIdx2sizeTab;//pageidx对应的size值,1k的整数倍

    // lookup table for sizeIdx <= smallMaxSizeIdx
    private final int[] sizeIdx2sizeTab;//在nSizes中idx对应的size值。size=>index

    // lookup table used for size <= lookupMaxclass
    // spacing is 1 << LOG2_QUANTUM, so the size of array is lookupMaxclass >> LOG2_QUANTUM
    private final int[] size2idxTab;//lookup范围内采样索引对应的nsizes的索引

    private int sizeClasses() {
        int normalMaxSize = -1;

        int index = 0;//数组索引
        int size = 0;

        int log2Group = LOG2_QUANTUM;
        int log2Delta = LOG2_QUANTUM;//log2Delta即与上一组size的差值的log2。可以理解为一组内以为个倍数增长
        int ndeltaLimit = 1 << LOG2_SIZE_CLASS_GROUP;//delta增量限制，这里设置每组增加为4个，所以ndeltaLimit=4。此处4个为一组的原因是移动4位刚好是1Byte

        //First small group, nDelta start at 0.
        //first size class is 1 << LOG2_QUANTUM
        int nDelta = 0;
        while (nDelta < ndeltaLimit) {//初始化第一组的四个特殊的sizeClass
            size = sizeClass(index++, log2Group, log2Delta, nDelta++);//四个数据含义，索引、组，组增量、组内增量
        }
        //后续组中log2Group比log2Delta大LOG2_SIZE_CLASS_GROUP,并且nDelta会从1走到1 << LOG2_SIZE_CLASS_GROUP
        //这则可以保证size = (1 << log2Group) + (1 << log2Delta) * nDelta在nDelta=1 << LOG2_SIZE_CLASS_GROUP
        //是size=1<<(1+log2Group)
        log2Group += LOG2_SIZE_CLASS_GROUP;

        //All remaining groups, nDelta start at 1.
        while (size < chunkSize) {
            nDelta = 1;
            //生成一组数据nDeleta从1到1 << LOG2_SIZE_CLASS_GROUP
            //表示这一组的数据中相邻两个size的差值为1<<nDelta
            while (nDelta <= ndeltaLimit && size < chunkSize) {
                size = sizeClass(index++, log2Group, log2Delta, nDelta++);
                normalMaxSize = size;
            }

            log2Group++;
            log2Delta++;
        }

        //chunkSize must be normalMaxSize，16777216
        assert chunkSize == normalMaxSize;

        //return number of size index
        return index;
    }

    //calculate size class
    //index:表示的是每个size类型的索引
    //log2Group:表示的对应size的对应的组，用于计算对应的size。进行log2计算的组基础位移偏移量
    //log2Delata:表示的是和上一个sizeClass的差值的log2值，其实就是Dsize的log2值。进行log2计算的增量偏移量
    //nDelta:表示的是这一组中的delta乘值。本组内计算的倍数值，在一组内会自增加，另一组会重新计算
    //isMultipageSize:表示的是这个size是否是page的倍数。 如果是4K的倍数就分多页，如果小于4K。此处是8192，如果8192的整数倍就是，即按8192(x<<13)分页
    //isSubPage:表示其是否为一个subPage类型。 如果size小于32768就是子页，即4KB以下的大小（32768/8）
    //log2DeltaLookup:表示的是lookup的size的值即为log2Delata值。log2Group是否小于12，小于12为log2Delta，大于等于12为0

    /**
     * jemalloc论文中将其分为了三块,分别为Small,Large和Huge。其中Small和Large是在Arena中分配的，而Huge则是直接在Arena之外进行分配的。
     * samll区域分为三个,size分别为：
     *   tiny:2B-8B
     *   quantum-spaced:16B-512B
     *   sub-page:1K-2K
     * large:4k-1m
     * Huge:2m以上
     *
     * 综合以上分析，
     * isSubPage：是区分large与small的变量
     * log2DeltaLookup：是区分quantum-spaced
     *
     * 所以：
     *  tiny部分为第一个sizeclas组，即log2Group第一个组
     *  quantum-spaced为除tiny部分外，log2DeltaLookup不为零的部分组
     *  sub-page为log2DeltaLookup为零部分开始，到isSubPage为零部分开始
     *  large为剩余部分
     *  huge堆外分配
     *
     * 参考：https://blog.csdn.net/cq_pf/article/details/107767775
     * @param index
     * @param log2Group
     * @param log2Delta
     * @param nDelta
     * @return
     */

    //sizeClass初始化
    private int sizeClass(int index, int log2Group, int log2Delta, int nDelta) {
        short isMultiPageSize;
        if (log2Delta >= pageShifts) {//如果大于8192（2的13次方）就直接是多页
            isMultiPageSize = yes;
        } else {
            int pageSize = 1 << pageShifts;//页大小，即8192
            int size = (1 << log2Group) + (1 << log2Delta) * nDelta;//本次size大小，算法就是2的log2Group次方，与2的log2Delta次的乘以nDelta之和

            isMultiPageSize = size == size / pageSize * pageSize? yes : no;//是否是pageSize的整数部
        }
        //log2Ndelta代表nDelta的log2的值
        int log2Ndelta = nDelta == 0? 0 : log2(nDelta);//nDelta只有第一个组为0，其它时候都不为0，log2(nDelta)方法代表的是nDelta这个最高1位的位置

        byte remove = 1 << log2Ndelta < nDelta? yes : no;
        //2^(log2Delta+log2Ndelta)即为(1 << log2Delta) * nDelta,故log2Delta + log2Ndelta == log2Group是size=2^(log2Group + 1)
        int log2Size = log2Delta + log2Ndelta == log2Group? log2Group + 1 : log2Group;
        if (log2Size == log2Group) {
            remove = yes;
        }
        //标记是否是subpage区域
        short isSubpage = log2Size < pageShifts + LOG2_SIZE_CLASS_GROUP? yes : no;//如果size小于32768就是子页，即4KB以下的大小（32768/8）

        int log2DeltaLookup = log2Size < LOG2_MAX_LOOKUP_SIZE ||
                              log2Size == LOG2_MAX_LOOKUP_SIZE && remove == no
                ? log2Delta : no;

        short[] sz = {
                (short) index, (short) log2Group, (short) log2Delta,
                (short) nDelta, isMultiPageSize, isSubpage, (short) log2DeltaLookup
        };

        sizeClasses[index] = sz;
        int size = (1 << log2Group) + (nDelta << log2Delta);//当前组大小

        if (sz[PAGESIZE_IDX] == yes) {//多页数量
            nPSizes++;
        }
        if (sz[SUBPAGE_IDX] == yes) {//子页数量
            nSubpages++;
            smallMaxSizeIdx = index;
        }
        if (sz[LOG2_DELTA_LOOKUP_IDX] != no) {
            lookupMaxSize = size;
        }
        return size;
    }
    //sizeClasses的size和page与index的对应关系
    private void idx2SizeTab(int[] sizeIdx2sizeTab, int[] pageIdx2sizeTab) {
        int pageIdx = 0;

        for (int i = 0; i < nSizes; i++) {
            short[] sizeClass = sizeClasses[i];
            int log2Group = sizeClass[LOG2GROUP_IDX];
            int log2Delta = sizeClass[LOG2DELTA_IDX];
            int nDelta = sizeClass[NDELTA_IDX];

            int size = (1 << log2Group) + (nDelta << log2Delta);//计算size
            sizeIdx2sizeTab[i] = size;//sizeIdex对应的size值

            if (sizeClass[PAGESIZE_IDX] == yes) {
                pageIdx2sizeTab[pageIdx++] = size;//pageIdx对应的size值
            }
        }
    }
    //
    private void size2idxTab(int[] size2idxTab) {
        int idx = 0;
        int size = 0;

        for (int i = 0; size <= lookupMaxSize; i++) {
            int log2Delta = sizeClasses[i][LOG2DELTA_IDX];
            int times = 1 << log2Delta - LOG2_QUANTUM;//每个索引采样次数

            while (size <= lookupMaxSize && times-- > 0) {
                size2idxTab[idx++] = i;
                size = idx + 1 << LOG2_QUANTUM;
            }
        }
    }

    @Override
    public int sizeIdx2size(int sizeIdx) {
        return sizeIdx2sizeTab[sizeIdx];
    }

    @Override
    public int sizeIdx2sizeCompute(int sizeIdx) {
        int group = sizeIdx >> LOG2_SIZE_CLASS_GROUP;
        int mod = sizeIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;

        int groupSize = group == 0? 0 :
                1 << LOG2_QUANTUM + LOG2_SIZE_CLASS_GROUP - 1 << group;

        int shift = group == 0? 1 : group;
        int lgDelta = shift + LOG2_QUANTUM - 1;
        int modSize = mod + 1 << lgDelta;

        return groupSize + modSize;
    }

    @Override
    public long pageIdx2size(int pageIdx) {
        return pageIdx2sizeTab[pageIdx];
    }

    @Override
    public long pageIdx2sizeCompute(int pageIdx) {
        int group = pageIdx >> LOG2_SIZE_CLASS_GROUP;
        int mod = pageIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;

        long groupSize = group == 0? 0 :
                1L << pageShifts + LOG2_SIZE_CLASS_GROUP - 1 << group;

        int shift = group == 0? 1 : group;
        int log2Delta = shift + pageShifts - 1;
        int modSize = mod + 1 << log2Delta;

        return groupSize + modSize;
    }

    @Override
    public int size2SizeIdx(int size) {
        if (size == 0) {
            return 0;
        }
        if (size > chunkSize) {
            return nSizes;
        }

        if (directMemoryCacheAlignment > 0) {
            size = alignSize(size);
        }

        if (size <= lookupMaxSize) {
            //size-1 / MIN_TINY
            return size2idxTab[size - 1 >> LOG2_QUANTUM];
        }

        int x = log2((size << 1) - 1);
        int shift = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
                ? 0 : x - (LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM);

        int group = shift << LOG2_SIZE_CLASS_GROUP;

        int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
                ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;

        int deltaInverseMask = -1 << log2Delta;
        int mod = (size - 1 & deltaInverseMask) >> log2Delta &
                  (1 << LOG2_SIZE_CLASS_GROUP) - 1;

        return group + mod;
    }

    @Override
    public int pages2pageIdx(int pages) {
        return pages2pageIdxCompute(pages, false);
    }

    @Override
    public int pages2pageIdxFloor(int pages) {
        return pages2pageIdxCompute(pages, true);
    }
    //这个方法其实就是根据给定的页数来计算出其对应的页的序号，其获取的则是下面表格中最后一列的数值，即为isMultiPageSize是1时从0开始的对size的编号，这个方法主要的作用是在PoolChunk中进行调用。
    //即pageIdx2sizeTab这个反向查找
    private int pages2pageIdxCompute(int pages, boolean floor) {
        int pageSize = pages << pageShifts;
        if (pageSize > chunkSize) {
            return nPSizes;
        }

        int x = log2((pageSize << 1) - 1);

        int shift = x < LOG2_SIZE_CLASS_GROUP + pageShifts
                ? 0 : x - (LOG2_SIZE_CLASS_GROUP + pageShifts);

        int group = shift << LOG2_SIZE_CLASS_GROUP;

        int log2Delta = x < LOG2_SIZE_CLASS_GROUP + pageShifts + 1?
                pageShifts : x - LOG2_SIZE_CLASS_GROUP - 1;

        int deltaInverseMask = -1 << log2Delta;
        int mod = (pageSize - 1 & deltaInverseMask) >> log2Delta &
                  (1 << LOG2_SIZE_CLASS_GROUP) - 1;

        int pageIdx = group + mod;

        if (floor && pageIdx2sizeTab[pageIdx] > pages << pageShifts) {
            pageIdx--;
        }

        return pageIdx;
    }

    // Round size up to the nearest multiple of alignment.
    private int alignSize(int size) {
        int delta = size & directMemoryCacheAlignment - 1;
        return delta == 0? size : size + directMemoryCacheAlignment - delta;
    }

    @Override
    public int normalizeSize(int size) {
        if (size == 0) {
            return sizeIdx2sizeTab[0];
        }
        if (directMemoryCacheAlignment > 0) {
            size = alignSize(size);
        }

        if (size <= lookupMaxSize) {
            int ret = sizeIdx2sizeTab[size2idxTab[size - 1 >> LOG2_QUANTUM]];
            assert ret == normalizeSizeCompute(size);
            return ret;
        }
        return normalizeSizeCompute(size);
    }

    private static int normalizeSizeCompute(int size) {
        int x = log2((size << 1) - 1);
        int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
                ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
        int delta = 1 << log2Delta;
        int delta_mask = delta - 1;
        return size + delta_mask & ~delta_mask;
    }
}
